home *** CD-ROM | disk | FTP | other *** search
/ Amiga Format CD 42 / Amiga Format AFCD42 (Issue 126, Aug 1999).iso / -serious- / programming / other / jikes / src / tuple.h < prev    next >
C/C++ Source or Header  |  1999-05-14  |  13KB  |  465 lines
  1. // $Id: tuple.h,v 1.3 1999/01/25 20:00:32 shields Exp $
  2. //
  3. // This software is subject to the terms of the IBM Jikes Compiler
  4. // License Agreement available at the following URL:
  5. // http://www.ibm.com/research/jikes.
  6. // Copyright (C) 1996, 1998, International Business Machines Corporation
  7. // and others.  All Rights Reserved.
  8. // You must accept the terms of that agreement to use this software.
  9. //
  10. #ifndef TUPLE_INCLUDED
  11. #define TUPLE_INCLUDED
  12.  
  13. #ifdef WIN32_FILE_SYSTEM
  14. #include <windows.h>
  15. #endif
  16.  
  17. #include "config.h"
  18. #include <string.h>
  19. #include <stdlib.h>
  20. #include <stdio.h>
  21. #include <assert.h>
  22. #include "bool.h"
  23.  
  24. class OutputBuffer;
  25.  
  26. //
  27. // This Tuple template class can be used to construct a dynamic
  28. // array of arbitrary objects. The space for the array is allocated in
  29. // blocks of size 2**LOG_BLKSIZE. In declaring a tuple the user
  30. // may specify an estimate of how many elements he expects.
  31. // Based on that estimate, suitable value will be calsulated log_blksize
  32. // and base_increment. If these estimates are off, more space will be 
  33. // allocated.
  34. //
  35. template <class T>
  36. class Tuple
  37. {
  38. protected:
  39.  
  40.     friend class OutputBuffer;
  41.  
  42.     enum { DEFAULT_LOG_BLKSIZE = 3, DEFAULT_BASE_INCREMENT = 4 };
  43.  
  44.     T **base;
  45.     int base_size,
  46.         top,
  47.         size;
  48.  
  49.     int log_blksize,
  50.         base_increment;
  51.  
  52.     inline int Blksize() { return (1 << log_blksize); }
  53.  
  54.     //
  55.     // Allocate another block of storage for the dynamic array.
  56.     //
  57.     inline void AllocateMoreSpace()
  58.     {
  59.         //
  60.         // The variable size always indicates the maximum number of
  61.         // elements that has been allocated for the array.
  62.         // Initially, it is set to 0 to indicate that the array is empty.
  63.         // The pool of available elements is divided into segments of size
  64.         // 2**log_blksize each. Each segment is pointed to by a slot in
  65.         // the array base.
  66.         //
  67.         // By dividing size by the size of the segment we obtain the
  68.         // index for the next segment in base. If base is full, it is
  69.         // reallocated.
  70.         //
  71.         //
  72.         int k = size >> log_blksize; /* which segment? */
  73.     
  74.         //
  75.         // If the base is overflowed, reallocate it and initialize the new elements to NULL.
  76.         //
  77.         if (k == base_size)
  78.         {
  79.             int old_base_size = base_size;
  80.             T **old_base = base;
  81.     
  82.             base_size += base_increment;
  83.             base = new T*[base_size];
  84.     
  85.             if (old_base != NULL)
  86.             {
  87.                 memmove(base, old_base, old_base_size * sizeof(T *));
  88.                 delete [] old_base;
  89.             }
  90.             memset(&base[old_base_size], 0, (base_size - old_base_size) * sizeof(T *));
  91.         }
  92.     
  93.         //
  94.         // We allocate a new segment and place its adjusted address in 
  95.         // base[k]. The adjustment allows us to index the segment directly,
  96.         // instead of having to perform a subtraction for each reference.
  97.         // See operator[] below.
  98.         //
  99.         base[k] = new T[Blksize()];
  100.         base[k] -= size;
  101.     
  102.         //
  103.         // Finally, we update SIZE.
  104.         //
  105.         size += Blksize();
  106.     
  107.         return;
  108.     }
  109.  
  110. public:
  111.  
  112.     //
  113.     // This function is invoked with an integer argument n. It ensures
  114.     // that enough space is allocated for n elements in the dynamic array.
  115.     // I.e., that the array will be indexable in the range  (0..n-1)
  116.     //
  117.     // Note that this function can be used as a garbage collector.  When
  118.     // invoked with no argument(or 0), it frees up all dynamic space that
  119.     // was allocated for the array.
  120.     //
  121.     inline void Resize(const int n = 0)
  122.     {
  123.         //
  124.         // If array did not previously contain enough space, allocate
  125.         // the necessary additional space. Otherwise, if the array had
  126.         // more blocks than are needed, release the extra blocks.
  127.         //
  128.         if (n > size)
  129.         {
  130.             do
  131.             {
  132.                 AllocateMoreSpace();
  133.             } while (n > size);
  134.         }
  135.         else if (n < size)
  136.         {
  137.             // slot is the index of the base element whose block
  138.             // will contain the (n-1)th element.
  139.             int slot = (n <= 0 ? -1 : (n - 1) >> log_blksize);
  140.     
  141.             for (int k = (size >> log_blksize) - 1; k > slot; k--)
  142.             {
  143.                 size -= Blksize();
  144.                 base[k] += size;
  145.                 delete [] base[k];
  146.                 base[k] = NULL;
  147.             }
  148.     
  149.             if (slot < 0)
  150.             {
  151.                 delete [] base;
  152.                 base = NULL;
  153.                 base_size = 0;
  154.             }
  155.         }
  156.     
  157.         top  = n;
  158.     }
  159.  
  160.     //
  161.     // This function is used to reset the size of a dynamic array without
  162.     // allocating or deallocting space. It may be invoked with an integer 
  163.     // argument n which indicates the new size or with no argument which
  164.     // indicates that the size should be reset to 0.
  165.     //
  166.     inline void Reset(const int n = 0)
  167.     {
  168.         assert(n >= 0 && n <= size);
  169.         top = n;
  170.     }
  171.  
  172.     //
  173.     // Return length of the dynamic array.
  174.     //
  175.     inline int Length() { return top; }
  176.  
  177.     //
  178.     // Return a reference to the ith element of the dynamic array.
  179.     //
  180.     // Note that no check is made here to ensure that 0 <= i < top.
  181.     // Such a check might be useful for debugging and a range exception
  182.     // should be thrown if it yields true.
  183.     //
  184.     inline T& operator[](const int i)
  185.     {
  186.         assert(i >= 0 && i < top);
  187.         return base[i >> log_blksize][i];
  188.     }
  189.  
  190.     //
  191.     // Add an element to the dynamic array and return the top index.
  192.     //
  193.     inline int NextIndex()
  194.     {
  195.         int i = top++;
  196.         if (i == size)
  197.             AllocateMoreSpace();
  198.         return i;
  199.     }
  200.  
  201.     //
  202.     // Add an element to the dynamic array and return a reference to
  203.     // that new element. 
  204.     //
  205.     inline T& Next() { int i = NextIndex(); return base[i >> log_blksize][i]; }
  206.  
  207.     //
  208.     // Assignment of a dynamic array to another.
  209.     //
  210.     inline Tuple<T>& operator=(const Tuple<T>& rhs)
  211.     {
  212.         if (this != &rhs)
  213.         {
  214.             Resize(rhs.top);
  215.             for (int i = 0; i < rhs.top; i++)
  216.                 base[i >> log_blksize][i] = rhs.base[i >> log_blksize][i];
  217.         }
  218.  
  219.         return *this;
  220.     }
  221.  
  222.     //
  223.     // Constructor of a Tuple
  224.     //
  225.     Tuple(unsigned estimate = 0)
  226.     {
  227.         if (estimate == 0)
  228.         {
  229.             log_blksize = DEFAULT_LOG_BLKSIZE;
  230.             base_increment = DEFAULT_BASE_INCREMENT;
  231.         }
  232.         else
  233.         {
  234.             for (log_blksize = 1; (((unsigned) 1 << log_blksize) < estimate) && (log_blksize < 31); log_blksize++)
  235.                 ;
  236.             if (log_blksize <= DEFAULT_LOG_BLKSIZE)
  237.                 base_increment = 1;
  238.             else if (log_blksize < 13)
  239.             {
  240.                 base_increment = (unsigned) 1 << (log_blksize - 4);
  241.                 log_blksize = 4;
  242.             }
  243.             else
  244.             {
  245.                 base_increment = (unsigned) 1 << (log_blksize - 8);
  246.                 log_blksize = 8;
  247.             }
  248.             base_increment++; // add a little margin to avoid reallocating the base.
  249.         }
  250.  
  251.         base_size = 0;
  252.         size = 0;
  253.         top = 0;
  254.         base = NULL;
  255.     }
  256.  
  257.     //
  258.     // Constructor of a Tuple
  259.     //
  260.     Tuple(int log_blksize_, int base_increment_) : log_blksize(log_blksize_),
  261.                                                    base_increment(base_increment_)
  262.     {
  263.         base_size = 0;
  264.         size = 0;
  265.         top = 0;
  266.         base = NULL;
  267.     }
  268.  
  269.     //
  270.     // Initialization of a dynamic array.
  271.     //
  272.     Tuple(const Tuple<T>& rhs) : log_blksize(rhs.log_blksize),
  273.                                  base_increment(rhs.base_increment)
  274.     {
  275.         base_size = 0;
  276.         size = 0;
  277.         base = NULL;
  278.         *this = rhs;
  279.     }
  280.  
  281.     //
  282.     // Destructor of a dynamic array.
  283.     //
  284.     ~Tuple() { Resize(0); }
  285.  
  286.     // ********************************************************************************************** //
  287.  
  288.     //
  289.     // Return the total size of temporary space allocated.
  290.     //
  291.     inline size_t SpaceAllocated(void)
  292.     {
  293.         return ((base_siz